/**
 * @description 快速排序
 */

export function quickSort(arr: number[]): number[] {
	const length = arr.length
	if (!length) return arr

	const midIndex = Math.floor(length / 2)
	const midValue = arr[midIndex]

	const left: number[] = []
	const right: number[] = []

	for (let i = 0; i < arr.length; i++) {
		if (i !== midIndex) {
			const n = arr[i]

			if (n < midValue) {
				left.push(n)
			} else {
				right.push(n)
			}
		}
	}

	return quickSort(left).concat([midValue], quickSort(right))
}
const arr = [1, 2, 6, 7, 3, 8, 4, 5, 9]
console.log(quickSort(arr))
